/*
归并排序:将两个有序数列合并成一个有序数列，我们称之为"归并"。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果

2. 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

 */


function merge_sort(array) {
    if (!array) return;
    var len = array.length;
    if (len < 2) return array;
    var mid = Math.floor(len / 2);
    var l_arr = merge_sort(array.slice(0, mid));
    var r_arr = merge_sort(array.slice(mid, len));

    return merge(l_arr, r_arr);
}

function merge(l_arr, r_arr) {
    var l_idx = 0,
        r_idx = 0,
        l_len = l_arr.length,
        r_len = r_arr.length;

    var result = [];
    while (l_idx < l_len && r_idx < l_len) {
        if (l_arr[l_idx] <= r_arr[r_idx]) {
            result.push(l_arr[l_idx]);
            l_idx++;
        } else {
            result.push(r_arr[r_idx]);
            r_idx++;
        }
    }
    result = result.concat(l_arr.slice(l_idx));
    result = result.concat(r_arr.slice(r_idx));
    return result;
}


var arr = [32, 42, 1, 89, 23, 154, 79, 81, 66, 7];
arr = merge_sort(arr);


console.log('merge sort:');
console.log(arr);